Dot products in Galois rings

(updated )

$$ \gdef\vec#1{\mathbf#1} \gdef\mat#1{\mathrm#1} \gdef\setn#1{\mathcal#1} \gdef\p#1{\left({#1}\right)} $$

(These are my notes from studying an idea worked out by Bryan Gillespie)

Galois Rings

Informally, a Galois ring is a generalisation of a Galois field $𝔽_{p^m}$ to have coefficients from the ring of integers modulo $p^s$ for some $s ≥ 1$. It inherits much of the structure of the field, and many applications of Galois fields can be generalized to work on Galois rings. This is useful as $ℤ_{2^k}$ can be efficiently implemented on computers.

Definition, existence and uniqueness

Definition. (Wan11 14.1) A Galois ring $R$ is a finite commutative ring with identity such that that the set of its zero divisors with $0$ added forms a principal ideal $(p)$ for some prime number $p$.

Theorem. (Wan11 14.2) The unique maximal ideal of $R$ is $(p)$ and $R/(p)$ is the Galois field $𝔽_{p^m}$ for some $m≥1$. The characteristic of $R$ is $p^s$ for some $s ≥ 1$.

Theorem. (Wan11 14.7) $R$ is uniquely determined (up to isomorphism) by $(p,s,m)$.

Theorem. (Wan11 14.4) The cardinality $|R|=p^{s⋅m}$.

Theorem. (Wan11 13.9) For any prime $p$, $s ≥ 1$ and $m ≥ 1$ there exists a Galois ring.

We can therefore speak of the Galois ring $GR(p^s, m)$.

Multiplicative group

Theorem. (Wan11 14.9) The group of units $R^×$ has order $|R^×| = (p^m - 1)⋅p^{(s-1)⋅m}$.

Theorem. An element $a ∈ R$ is a unit if and only if its equivalence class in $R/(p)=𝔽_{p^s}$ does not equal $0$.

From this follows a simple method to compute inverses by first testing the reduction mod $p$ against zero and exponentiating the element by $|R^×|-1$.

$x$ has order $(p^m - 1)⋅p^{s-1}$

Structure

Theorem. (Wan11 14.6) $R$ is isomorphic to the ring $ℤ_{p^s}[x] / (h(x))$ for any monic basic polynomial $h(x)$ of degree $m$ over $ℤ_{p^s}$.

In particular if $s=1$ then $R ≃ 𝔽_{p^m}$ and if $m = 1$ then $R ≃ ℤ_{p^s}$. As such Galois rings generalize over finite fields and integers modulo a prime power. Of particular interest are cases where $p=2$ which have efficient implementations.

Theorem. (Wan11 14.1) $R$ is a free $ℤ_{p^s}$-module of rank $m$.

Theorem. (Wan11 ex. 14.1 p. 367) For $1 ≤ r < s$ the quotient ring $R/(p^r)$ is isomorphic to $GR(p^r, m)$.

Theorem. (Wan11 14.24) For a positive divisor $n$ of $m$, $R$ contains a unique subring $GR(p^s, n)$.

$p$-addic representation

Theorem (Wan11 14.8) There exist a $ω ∈ R$ of order $p^m -1$ which is a root of a monic basic primitive polynomial $h(x)$ of degree $m$ over $ℤ_{p^s}$ and dividing $x^{p^m -1}-1$ in $ℤ_{p^s}[x]$. Let $$ \setn T = \{0, 1, ω, ω^2, …, ω^{p^m - 2}\} $$ be the set of then every element of $c ∈ R$ can be written uniquely in the form $$ c = c_0 + c_1 ⋅ p + c_2 ⋅p^2 + ⋯ + c_{s-1} ⋅ p^{s-1} $$ where $c_i ∈ \setn T$. Moreover $c$ is a unit if and only if $c_0 ≠ 0$ and $c$ is a zero divisor or $0$ if and only if $c_0 = 0$.

Note that $\setn T$, known as the Teichmüller representatives, are a lift from $𝔽_{p^m}$ to $R$.

Definition The generalized Frobenius map takes an element in $p$-addic representations an raises every coefficient to the $p$-th power: $$ ϕ: c_0 + c_1 ⋅ p + ⋯ + c_{s-1} ⋅ p^{s-1} ↦ c_0^{p} + c_1^{p} ⋅ p + ⋯ + c_{s-1}^{p} ⋅ p^{s-1} $$

Theorem. (Wan11 14.31) The automorphism group of $R$ is cyclic of order $m$ and generated by the Frobenius automorphism: $$ \operatorname{Aut}_{ℤ_{p^s}}(R) = ⟨ϕ⟩ $$

Bases

Definition. The trace of an element $a ∈ R$, denoted $\operatorname{Tr}(a)$ and norm, denoted $\operatorname{N}(a)$ are $$ \begin{aligned} \operatorname{Tr}(a) &= \!\!\!\!\!\sum_{i∈[0,m-1]}\!\!\! ϕ^i(a) &\quad \operatorname{N}(a) &= \!\!\!\!\!\prod_{i∈[0,m-1]}\!\!\!\! ϕ^i(a) & \end{aligned} $$

Theorem. (Wan11 14.34) $$ \begin{aligned} \operatorname{Tr}(a) &∈ ℤ_{p^m} \\ \operatorname{Tr}(a + b) &= \operatorname{Tr}(a) + \operatorname{Tr}(b) \\ \operatorname{Tr}(c ⋅ a) &= c⋅\operatorname{Tr}(a) \\ \operatorname{Tr}(c) &= m ⋅ c \\ \operatorname{Tr}(ϕ(a)) &= \operatorname{Tr}(a) \\ \end{aligned} $$

Question. Is $\operatorname{Tr}(a⋅b)$ an inner product?

Definition. (Wan11 8.2) Two bases $\set{a_1, a_2, …, a_n}$ and $\set{b_1, b_2, …, b_n}$ are said to be equivalent if there exist an $e ∈ 𝔽_p$ such that $a_i = e⋅b_i$ and weakly equivalent if there exist and $e ∈ R$ such that $a_i = e⋅b_i$.

Question. What are all the bases of a Galois ring up to permutation and weak equivalence?

Products in Galois Ring Representations

(See also Wan11 p. 164)

Represent $R$ by $ℤ_{p^s}[x] / h(x)$ for some $h$, then $\setn X = \set{ x^i }$ is the monomial basis that creates an isomorphism with $ℤ_{p^s}^m$.

The Frobenius automorphism group $ϕ$ becomes a linear operator and can be represented by a matrix $\mat F$ of order $m$.

Question. What are all the isomorpisms $GR(p^s, m) → ℤ_{p^s}^m$ that can be constructed? We can change $h$ and change the choice of basis. The result must equal the automorphism group

$$ \operatorname{Aut}_{ℤ_{p^s}}(ℤ_{p^s}^m) ≃ \operatorname{GL}_{m}(ℤ_{p^s}) $$

Hypothesis. Changes of basis on $ℤ_{p^s}[x] / h(x)$ are in one-to-one correspondence with matrices $\operatorname{GL}_{m}(ℤ_{p^s})$.

Hypothesis. The $ℤ_{p^s}$-module automorphisms are also ring homomorphisms by an appropriate transformation of the bilinear map for ring products.

Theorem. (Wan11 14.32) Given Galois ring $R=GR(p^s, m)$ with subring $R'=GR(p^s, n)$, the automorphism group of $R$ over $R'$ is isomorphic to the automorphism group over their residue fields. $$ \operatorname{Aut}_{R'}(R) ≃ \operatorname{Aut}_{𝔽_{p^n}}(𝔽_{p^m}) $$

So every automorphism of a Galois ring is a power of the generalized Frobenius automorphism.

$$ σ(n) = n^{p^m} $$

Note. The automorphism group of $B$ over $A$, denoted $\operatorname{Aut}_{A}(B)$ here following Wan11, is also commonly denoted $\operatorname{Aut}(B/ A)$. When $A$ and $B$ are Galois fields, this group is typically denoted $\operatorname{Gal}(B / A)$.

Under this isomorphism the $R$-product becomes a symmetric bilinear map $ℤ_{p^s}^m × ℤ_{p^s}^m → ℤ_{p^s}^m$. Such bilinear maps are uniquely characterized by a rank-3 tensor $m ∈ ℤ_{p^s}^{m^3}$ defined by:

$$ x^k ⋅ x^l = \sum_{r} m_{klr} ⋅ x^r $$

The $m$ values depend on the choice of $h$ and basis.

The $m$ values are constraint by the automorphism group as the product needs to satisfy

$$ a ⋅ b = ϕ^{-k}(ϕ^k(a) ⋅ ϕ^k(b)) $$

Question. What are other constraints to make this a valid product? It needs to be bilinear, symmetric. Basically needs to satisfy the ring axioms? Distributivity follows from bilinearity. Missing is identity and associativity. What about compatibility with the scalar product?

The ring product operation is a symmetric bilinear map over the module. Given two bases $\setn U = \set{\vec u_i}$ and $\setn V = \set{\vec v_i}$ for $R$ we can represent the product in coordinates as:

$$ a ⋅ b = \sum_k a^{\setn U}_i ⋅ b^{\setn U}_j ⋅ m_{ijk} ⋅ \vec v_k $$

where $a^{\setn U}_i, b^{\setn U}_j ∈ ℤ_{p^s}$ are coordinates of $a, b$ in basis $\setn U$ and $m$ is a rank-$3$ tensor over $ℤ_{p^s}$ with coordinates given by

$$ m_{ijk} = (\vec u_i ⋅ \vec u_j)^{\setn V}_k $$

Observe that each product coordinate $(a ⋅ b)^{\setn V}_k$ is a symmetric bilinear form on the input coordinates. This let's us state our main question:

Question. Which symmetric bilinear forms on $ℤ_{p^s}^m$ can be constructed by appropriate choices of $\setn U$ and $\setn V$?

Computing Bilinear Forms

Without loss of generality we can focus on the first output coordinate $\vec v_0$. Given a bilinear form $\mat B_{ij}$, we need

$$ m_{ij0} = (\vec u_i ⋅ \vec u_j)^{\setn V}_0 = \delta_{ij} $$

Represent $R$ by $ℤ_{p^s}[x] / h(x)$ for some $h$, then $\setn X = \set{ x^i }$ is a basis. We can represent the transformation from $\setn X$ to $\setn U$ and $\setn V$ by invertible matrices $u_{ij} = (x^i)^{\setn U}_j$ and $v_{ij} = (x^i)^{\setn V}_j$.

$$ x^k ⋅ x^l = \sum_{r} m_{klr} ⋅ x^r $$

In the target bases

$$ \vec u_i = \sum_j u_{ij} ⋅ x^j $$

where $u_{ij} = (\vec u_i)^{\setn X}_j$ and similarly for $\setn V$.

$$ x^r = \sum_{q} v_{rq} ⋅ \vec v_q $$

where $v_{rq} = (x^r)^{\setn V}_q$. Then

$$ \begin{aligned} \vec u_i ⋅ \vec u_j &= \p{\sum_k u_{ik} ⋅ x^k} ⋅ \p{\sum_l u_{jl} ⋅ x^l} \\ &= \sum_k \sum_l u_{ik} ⋅ u_{jl} ⋅ \p{x^k ⋅ x^l} \\ &= \sum_k \sum_l \sum_r u_{ik} ⋅ u_{jl} ⋅ m_{klr} ⋅ x^r \\ &= \sum_k \sum_l \sum_r \sum_q u_{ik} ⋅ u_{jl} ⋅ m_{klr} ⋅ v_{rq} ⋅ \vec v_q \\ (\vec u_i ⋅ \vec u_j)^{\setn V}_q &= \sum_k \sum_l \sum_r u_{ik} ⋅ u_{jl} ⋅ m_{klr} ⋅ v_{rq} \end{aligned} $$

This is a polynomial system of equations in unknowns $u_{ij}$ and $v_{ij}$.

$$ u_i^T ⋅ M_r ⋅ u_j $$

Example: the Galois ring $ℤ_{2^{16}}[x] / (x^4 -x - 1)$

In $R = ℤ_{2^{16}}[x] / (x^4 -x - 1)$ with basis $\{ x^i \}$ we have multiplication represented by structure constants

$$ c = \begin{bmatrix}\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0& 1 \\ \end{pmatrix}, \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ \end{pmatrix}, \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ \end{pmatrix}, \begin{pmatrix} 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ \end{pmatrix} \end{bmatrix} $$ such that $x^i⋅x^j = \sum_k c_{ij}^k ⋅ x^k$. The order of the multiplicative group $|R^×| = 2^{60}⋅3⋅5$ with $\operatorname{ord}(x) = 2^{15}⋅3⋅5$. For $k$ dividing $\operatorname{ord}(x)$ we construct primitive $k$-th roots of unity $ω_k$ as $ω_k = x^\frac{\operatorname{ord}(x)}{k}$. In particular the generator of the Teichmüller set is $$ ω_{2^4-1} = 40289 + 46738⋅x + 59713⋅x^2 + 8880⋅x^3 $$ and the Frobenius map $ϕ$ of $R$ over $ℤ_{2^{16}}$ is represented by the matrix $$ \mat F = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 14104 & 36826 & 23545 & 3040 \\ 50161 & 28753 & 57364 & 20500 \\ 21492 & 33826 & 19639 & 36881 \end{bmatrix} $$ such that $ϕ(x^i) = \sum_j \mat F_{ij} ⋅ x^j$. $\mat F$ generates the automorphism group of the ring. The automorphism group of the module is the general linear group $\operatorname{GL}_4(ℤ_{2^{16}})$.

$$ \begin{aligned} (\vec u_i ⋅ \vec u_j)^{\setn V}_q &= \sum_k \sum_l \sum_r u_{ik} ⋅ u_{jl} ⋅ m_{klr} ⋅ v_{rq} \\ \end{aligned} $$

So we need to solve

$$ δ_{ij} = \sum_k \sum_l \sum_r u_{ik} ⋅ u_{jl} ⋅ m_{klr} ⋅ v_{r0} $$

where the lhs and $m_{klr}$ are constants, and $u$ and $v$ are invertible matrices. Ignoring the invertibility constraint, this is a system of $16$ polynomial equations in $20$ unknowns of degree $3$.

Question. Why are there exactly two solutions when we constrain the matrix to be unitriangular?

Question. Which symmetric bilinear forms can be computed simultaneously?

Question. If we pick two different bases for the input elements the coordinate bilinear forms are no longer symmetric. Which (not necessarily symmetric) bilinear forms can be constructed by an appropriate choice of basis?

Efficient Computation in MPC

The scheme is to be used inside an Shamir Secret Sharing setting. Let $(a_0, a_1, … a_n)$ be valid evaluation points, with the secret stored at $a_0$, then the secret $s$ is reconstructed from shares $s_i$ as

Claim. Given a Shamir secret sharing with secret evaluation point $x_s$ and party points $x_0,…x_{n-1}$ the parties can locally convert to additive sharing.

This follows from the observation that the Lagrange interpolation formula is a sum over locally computable terms $$ s = \sum_{i∈[1,n]} L_i(x_s) ⋅ s_i $$

Question. Are the $L_i(x_s)$ guaranteed to be units? Can we therefore always convert locally back from additive to Shamir sharing? Can this be generalized to any linear sharing scheme?

Claim. Given a linear map $p:U→V$ and an additive secret $s ∈ U$ such that $s = \sum_i s_i$, the parties can locally compute an additive sharing of $p(s)$:

$$ p(s) = p\!\p{\sum_i s_i} = \sum_i p(s_i) $$

So given a Shamir sharing of $s$ we can locally compute an additive sharing of $p(s)$.

Galois rings among $ℤ_{p^s}$-algebras

Take $ℤ_{p^s}^m$, the free $ℤ_{p^s}$-module of rank $m$, and a bilinear operation denoted as multiplication to form an algebra $A$. For a basis $\{\vec e_i\}$ multiplication is uniquely defined by the structure constants $c_{ij}^k ∈ ℤ_{p^s}$ given by $$ \vec e_i ⋅ \vec e_j= \sum_k c_{ij}^k ⋅ \vec e_k $$

We constrain $A$ to be commutative, unital and associative, which respectively imply

$$ c_{ij}^k = c_{ji}^k \\ \sum_i u_i ⋅ c_{ij}^k = δ_{jk} \\ \sum_l c_{ij}^l ⋅ c_{lk}^m = \sum_l c_{ik}^l ⋅ c_{jl}^m $$

where $u_i$ are the coordinates of the identity element in the basis.

Question. What are the (additional) requirements for $A$ to be a Galois ring?

Question. What other algebras are suitable for MPC?

To show that $A$ is a Galois ring by the definition above, all that remains is to show that "the set of its zero divisors with $0$ added forms a principal ideal $(p)$ for some prime number $p$". We already have that $(p)$ is an ideal, as this is inherited from $ℤ_{p^s}$.

References

Appendix: Solver

See the full source in galois-dot.rs and associated SageMath notebook galois-dot.ipynb.

To find solutions I wrote a little multi-threaded solver in Rust:

/// Solve polynomial systems of equations over `u64` by linear Hensel lifting.
/// 
/// `eval` should be a function that takes a solution vector and returns the
/// bitwise-or of the polynomial functions at that point.
fn root<const N: usize>(eval: impl Fn([u64; N]) -> u64 + Sync) -> Vec<[u64; N]> {
    let mut solutions = vec![[0; N]];
    for bit in 0..64 {
        println!("Lifting bit {}, initial solutions {}", bit, solutions.len());
        solutions.truncate(1000); // Limit number of candidate solutions to prevent explosion
        solutions = solutions.into_par_iter().flat_map(|solution| {
            (0..(1 << N)).into_par_iter().map(|bit_pattern| {
                std::array::from_fn(|i| solution[i] | (((bit_pattern >> i) & 1) << bit))
            }).filter(|&sol| eval(sol).trailing_zeros() > bit)
            .collect::<Vec<_>>()
        }).collect();
    }
    solutions
}

For example to compute the inverse of 5:

root(|[n]| n.wrapping_mul(5).wrapping_sub(1))

For example to find $2×2$ invertible matrices $m$ such that

$$ \begin{aligned} m_{00}⋅ m_{10}^3 &= m_{01} & m_{01}^3 &= 5 & m_{00}^5 &= 9 \end{aligned} $$

/// Check if a number is a unit by computing $1 - n^{2^{63}}$.
fn is_unit(mut v: Wrapping<u64>) -> Wrapping<u64> {
    (v & Wrapping(1)) ^ Wrapping(1) // Equivalent expression
}

fn equations(v: [u64; 4]) -> u64 {
    let [m00, m01, m10, m11] = v.map(Wrapping);
    let mut lhs = Wrapping(0);
    lhs |= is_unit(m00*m11 - m10*m01); // Determinant is a unit
    lhs |= m00*m10.pow(3) - m01;
    lhs |= m01.pow(3) - Wrapping(5);
    lhs |= m00.pow(5) - Wrapping(9);
    lhs.0
}

println!("Solutions {:?}", root(equations));

There's room for optimization. The is_unit checks can be dismissed after the first bits are found. Linear constraints can be solved first to reduce the number of variables.

Remco Bloemen
Math & Engineering
https://2π.com